SRM 449

Match Summary

Round Overview
Discuss this match

MountainRoad

Used as: Division Two - Level One:

There are 2 easy ways of solving this.

• a) If you look at the triangle between (0,x) , you can see that it either goes up or goes down .

  • The total path length between 0 and x is x. Intersections don’t change the path length because if you intersect , you either change direction or continue the direction.

    • So answer is sqrt(2)*(max(finish) - min(start))

• b) Scale the start and finish time by 2, so that the length between them is always even.

  • Now path from (0,x) becomes (0,2x) .From (0,x) we go upwards , (x,0) we go downwards.

  • So in (start,end),mid=(start+end)/2 until mid we go up and from mid we go down.

  • Let origin be 2500 in an array of 5000 namely f.

    • The height at index x of array f namely f(x) is the max height y attainable by all triangles. We can just fill the f for all triangles.

    • Now between 2 indices (i,i+1) the change in vertical distance is 0 or 1. The total distance is the sum across the array for all indices. But this distance is twice the actual distance as we scaled up.Divide by 2 and multiply by sqrt(2) to get answer.
      Example : for (0,1) we do (0,2) , then the array f[] is 0,1,0.For this path length is 2. The y distance of 1 is actual distance y distance of 1/2 and a path length of sqrt(2)/2 because corresponding x distance is always 1.

    • Number of triangles is small , it is of complexity O(5000 * N) where N is number of triangles.

• c) Another explanation (see above diagram):

  • Consider any pair of adjacent triangles in the list (e.g., the first two), there are two cases:

    • i) either one triangle completely contains the other, or

    • ii) they overlap as in the diagram. (It doesn’t matter which one is taller, the one on the left or the one on the right. In the diagram I’ve shown where the one on the right is taller, but the same argument holds if the one on the left is taller, just flip the image horizontally.) Extend AC and GF until they meet at point E. It’s not too hard to see that quadrilateral CDEF is a right parallelogram, so length(CD) == length(EF) and length(CE) == length(DF). Therefore walking ACDFG yields the same length path as walking ACEFG. But note that ACEFG is the the same as the triangle AEG. AEG is in fact an isoceles triangle (because angles EAG and EGA are both 45 degrees).

  • In both cases, these two adjacent triangles (A,B) and (H,G) contribute the same to the overall walking path as (A,G).

  • Since any two adjacent triangles contribute an equal path length to the single triangle ( min(start1, start2), max(end1, end2) ), this process can happen over and over until all triangles have been replaced by the single triangle ( min(start1, …, startN), max(end1, …, endN ).

  • The solution is therefore:

    • start = smallest of all starts

    • end = largest of all ends

    • answer = sqrt( 2 ) * (end - start)

OddDivisors

Used as: Division Two - Level Two:

• If we see, the greatest odd divisor that divides N is N if N is odd or if N is even the greatest odd divisor of N is F(N/2).

• For (1,N) if N is odd we get 1 + 3 + 5 + …N + F(2) + F(4)+…F(N-1). The greatest even N is F((N-1)/2).

• That means the sum F(2) + F(4)+…F(N-1) = F(1) + F(2) + F(3) + F((N-1)/2). Now this is our original problem with N as (N-1)/2.

• In case of N as even our problem is split into 1+3+5+ …N-1 and F(2)+ F(4) + …+ F(N), which is again sum(1,N/2).

• Now the sum of 1+3+5+…+N= (N+1)*(N+1)/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
long long get(int a, int x) {
  int n = (x - 1) / 2;
  n++;
  return (x + 1) * 1 LL * n / 2;
}

long long sum(int b) {
  if (b == 1) return 1;
  if (b == 2) return 2;
  if (b & 1) return sum((b - 1) / 2) + get(1, b);
  else return sum(b / 2) + get(1, b - 1);
}

class OddDivisors {
  public: long long findSum(int N) {
    return sum(N);
  }
};

An shorter, more elegant solution exists if one considers the fact that division of integers rounds down by default.

1
2
3
4
long long findSum(int N) {
  if (n == 0) return 0;
  return (ll)((n + 1) / 2) * ((n + 1) / 2) + findSum(n / 2);
}

HexagonalBattlefieldEasy

Used as: Division Two - Level Three:

• Since the constraints of this problem is smaller ie N<=4, we can enumerate all the choices. If N is odd we get 0, otherwise we can choose a cell and place a block in one of its adjacent vertices. Backtracking works and is fast. The max number of ways for N=4 is with (-3,-3) blocked it gives around ~ 120000 ways. Look at FameofLight’s backtracking solution in the practice room.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
int n;
int ret;
int dp[20][20];
int dx[] = {
  0,
  1,
  -1,
  1,
  -1,
  0
};
int dy[] = {
  1,
  1,
  0,
  0,
  -1,
  -1
};

void dfs(int x, int y, int d) {
  dp[x + 7][y + 7] = 1;
  if (d == 0) return;
  for (int i = 0; i < 6; i++) {
    dfs(x + dx[i], y + dy[i], d - 1);
  }
}

void solve() {
  int sx = -1, sy = -1;
  for (int i = -n; i <= n; i++) {
    for (int j = -n; j <= n; j++) {
      if (dp[i + 7][j + 7] == 1) {
        sx = i + 7;
        sy = j + 7;
        break;
      }
    }
    if (sx != -1) break;
  }
  if (sx == -1) {
    ret++;
    return;
  }
  dp[sx][sy] = 0;
  for (int i = 0; i < 6; i++) {
    if (dp[sx + dx[i]][sy + dy[i]] == 1) {
      dp[sx + dx[i]][sy + dy[i]] = 0;
      solve();
      dp[sx + dx[i]][sy + dy[i]] = 1;
    }
  }
  dp[sx][sy] = 1;
}

class HexagonalBattlefieldEasy {
  public: int countArrangements(vector < int > X, vector < int > Y, int N) {
    n = N;
    ret = 0;
    memset(dp, 0);
    dfs(0, 0, N - 1);
    For(i, size(X)) {
      dp[X[i] + 7][Y[i] + 7] = 0;
    }
    solve();
    return ret;
  }
};

• For more efficient version look at the solution of DIV 1 500 , which is same except the constraints are high as 8.

MaxTriangle

Used as: Division One - Level One:

• The crux of the problem lies in figuring out the maximum value c < 2*10^9 can take is 256 , it occurs for numbers 48612265 ,515290009 etc. Once we know this we can do it by brute force. This value can be computed by expressing the number in the form of non-gaussian primes (primes of form 4k+1). If the number C is expressed as C=K*(p1^a1)**(p2a2)(p3^a3)… Then the value of them is (a+1)(a2+1)**(a3+1). The K is for primes other than of form 4k+1. It is not required to know this but it could help.

• We are given a perfect square c. We have to find all the integer pairs (a,b) such that a^2 + b^2 = c. Now each of (a,b) (-a,b) (a,-b) and (-a,-b) satisfy the equation if (a,b) satisfies. We put these in a Avector and Bvector.

• Compute the area for each pair of Avector and Bvector. If we know the co-ordinates then we find the area using determinant or use the formula 1/2*a*b*sin(th).

• Also it is to be noted that if we have a valid pair that is collinear with another valid pair , a triangle is possible by reflecting the point across one of the axis.

HexagonalBattlefield

Used as: Division One - Level Two:

Hexagonal patterns and skewed coordinate axes initially may seem difficult to grasp, but fixing it takes just a slight twist that comes in useful whenever solving a problem in such a setting:

You might know that the general tiling problem is NP-complete.

Anyway, realize that trying all arrangements using brute force will time out. (You can quickly estimate that, for example, thinking about small 4 cell blocks: each can be arranged in two possible ways, and you can have lots of them in a maximum size test case.)

We need to think of an improvement. Let’s see about dynamic programming/memoization. Note that since each Vasyl’s hero occupies two neighboring cells, we can divide any valid arrangement by a jagged line passing along heroes’ borders so that, considering an x coordinate of x_d, cells belong to the left part iff the occupying hero lies partly or wholly at x < x_d. Identify a recurring subproblem as “how many ways there are to fill the space to the left of a given border”.

This needn’t be the only feasible way of dividing the field for the purpose of applying DP; it’s just arguably the most easily described one: one can encode such a state in a binary number (bit mask) using bit 1 if the cell belongs to the left part, 0 otherwise.

DP’s initial state is empty field, that is, border drawn at x_d = -2 and the mask is all zeros - there’s only one way to have that. The goal can be described as x_d = 3 (a dummy extra column) and all zeros mask.

There’s still the question whether this will run in time. Note that for the highest column there may be 2^(2*n-1) masks to consider; if we were to transit to each of the 2^(2*n-2) masks for the adjacent column, that would constitute 2^29 operations in the maximum case - too many. Instead for each mask we should carefully consider only adjacent column’s masks that actually correspond to possible arrangements of heroes - that can be implemented by backtracking. Proving that there are few enough valid transitions is exercisey.

StairsColoring

Used as: Division One - Level Three:

• The number of staircase configurations for size n is Catalan(n). Look in wikipedia page for Catalan numbers or rng_58 explanation in the forums.Let it be n.

• The answer is k^n mod p. We know that k^(p-1) mod p is 1 from fermats little theorem. So if we know n%(p-1)=r , then our answer is k^r mod p.

• The difficulty lies in calculating Catalan(n)%(p-1). The mod (p-1) can be computed because p-1=2*3*11*2089*7253.

• So if we have x=k{1} mod 2 , x= k{2} mod 3 , x=k{3} mod 11… , using the chinese remainder theorem we can find the smallest x that satisfies the equation. So we have reduce Catalan(n)%2,3,11 to plugin the values of k{i}'s.

• Once we find the smallest x the value can be computed.

• Now the problem is reduced to finding Binomial(N,k) mod p. This could be done by Lucas theorem or compute n! mod p * inverse of (k! mod p). This is explained by maxdiver at Binomial mod p

• Not to overlook is people solving it correctly, solving it in under 30 mins, AcRush under 15 minutes.